﻿#include <iostream>

#define MIN(a, b) (a < b ? a : b) 
#define IMPOSSIBLE_COST 0x1fffffff

// 表示src[i-1]变化到dst[j-1]的最小花费
static int recur(const char* src, const char* dst, const int insertCost, const int delCost, const int replaceCost, int i, int j)
{
	if (i == 0)
	{
		return j * insertCost;
	}

	if (j == 0)
	{
		return i * delCost;
	}

	// 以dst的第j-1个字符为基准
	// src[i-1]=>dst[j-2] 插入一个字符
	int cost1 = recur(src, dst, insertCost, delCost, replaceCost, i, j - 1) + insertCost;
	// src[i-2]=>dst[j-1] 删除一个字符
	int cost2 = recur(src, dst, insertCost, delCost, replaceCost, i - 1, j) + delCost;
	// src[i-2]=>dst[j-2] 替换一个字符
	int cost3 = recur(src, dst, insertCost, delCost, replaceCost, i - 1, j - 1) + replaceCost;
	// 当src[i-1]==dst[j-1]时，不需要额外的花费了
	int cost4 = IMPOSSIBLE_COST;
	if (src[i - 1] == dst[j - 1])
	{
		cost4 = recur(src, dst, insertCost, delCost, replaceCost, i - 1, j - 1);
	}

	return MIN(MIN(cost1, cost2), MIN(cost3, cost4));
}

static void calcCost(int* dp, const char* src, const char* dst, const int insertCost, const int delCost, const int replaceCost, size_t srcSize, size_t dstSize, int i, int j)
{
	if (i + j * srcSize < srcSize * dstSize && dp[i + j * srcSize] != IMPOSSIBLE_COST)
	{
		return;
	}

	int cost1 = IMPOSSIBLE_COST;
	if (i < srcSize && j - 1 < dstSize)
	{
		cost1 = dp[i + (j - 1) * srcSize] + insertCost;
	}

	int cost2 = IMPOSSIBLE_COST;
	if (i - 1 < srcSize && j < dstSize)
	{
		cost2 = dp[i - 1 + j * srcSize] + delCost;
	}

	int cost3 = IMPOSSIBLE_COST;
	if (i - 1 < srcSize && j - 1 < dstSize)
	{
		cost3 = dp[i - 1 + (j - 1) * srcSize] + replaceCost;
	}

	int cost4 = IMPOSSIBLE_COST;
	if (i - 1 < srcSize && j - 1 < dstSize && src[i - 1] == dst[j - 1])
	{
		cost4 = dp[i - 1 + (j - 1) * srcSize];
	}

	dp[i + j * srcSize] = MIN(MIN(cost1, cost2), MIN(cost3, cost4));
}

static int byStrictTable(const char* src, const char* dst, const int insertCost, const int delCost, const int replaceCost)
{
	auto srcSize = strlen(src) + 1;
	auto dstSize = strlen(dst) + 1;
	int* dp = (int*)malloc(srcSize * dstSize * sizeof(int));
	int i;
	int j;
	for (j = 0; j < dstSize; j++)
	{
		for (i = 0; i < srcSize; i++)
		{
			dp[i + j * srcSize] = IMPOSSIBLE_COST;
		}
	}

	for (j = 0; j < dstSize; j++)
	{
		dp[j * srcSize] = j * insertCost;
	}

	for (i = 0; i < srcSize; i++)
	{
		dp[i] = i * delCost;
	}

	for (j = 1; j < dstSize; j++)
	{
		for (i = 1; i < srcSize; i++)
		{
			calcCost(dp, src, dst, insertCost, delCost, replaceCost, srcSize, dstSize, i, j);
		}
	}

	int res = dp[srcSize - 1 + (dstSize - 1) * srcSize];
	free(dp);
	return res;
}

// 给定两个字符串str1和str2，再给定三个整数ic、dc和rc，分别代表插入、删除和替换一个字符的代价，
// 返回将str1编辑成str2的最小代价。
// 举例:
//str1 = "abc", str2 = "adc", ic = 5, dc = 3, rc = 2
// 从"abc"编辑成"adc", 把'b'替换成'd'代价是最小的，所以返回2.
//
//str1 = "abc", str2 = "adc", ic = 5, dc = 3, rc = 100
// 从"abc"编辑成"adc", 先删除'b', 然后插入'd'是代价最小的，所以返回8
//
//str1 = "abc", str2 = "abc", ic = 5, dc = 3, rc = 2
// 不用编辑了，本来就是一样的字符串，所以返回0
//
//思路：
// 制作一张表，一个字符串作为行，另外一个字符串作为列。
// 设str1 = "abcdef", str2 = "skbcdf"
//
//
//s  k  b  c  d  f
// 0  1  2  3  4  5  6 (j)
// 0 ? ? ? ? ? ? ?
// a 1 ? ? ? ? ? ? ?
// b 2 ? ? ? ? ? ? ?
// c 3 ? ? ? ? ? ? ?
// d 4 ? ? ? ? ? ? ?
// e 5 ? ? ? ? ? ? ?
// f 6 ? ? ? ? ? ? ?
//(i)
//
//这张表的涵义是，str1前缀长度为i的字符串变化到str2前缀长度为j的字符串，最小代价是多少。
// 即，i = 0 表示str1前缀是空字符串，j = 0 表示str2前缀是空字符串.
// dp[i][j]就是str1[0...i - 1]变化到str2[0...j - 1]的最小代价是多少。
//
//可以先将str1或者str2前缀是空串的情况求解出：
//
//s    k      b     c     d     f
// 0       1    2      3     4     5     6     (j)
// 0  0      插入 插入 * 2 插入 * 3 插入 * 4 插入 * 5  插入 * 6
// a 1 删除
// b 2 删除 * 2
// c 3 删除 * 3
// d 4 删除 * 4
// e 5 删除 * 5
// f 6 删除 * 6
// (i)
//
//其余的普遍位置，可以分为几种情况: str1[0...i - 2, i - 1]->str2[0...j - 2, j - 1]
// 1. 将str1[0...i - 2]变成str2[0...j - 1], 然后删除str1[i - 1]
// dp[i][j] = dp[i - 1][j] + 删除代价
//
//2. 将str1[0...i - 1]变成str2[0...j - 2], 然后str1再追加一个字符：str2[j - 1]
// dp[i][j] = dp[i][j - 1] + 插入代价
//
//3. 将str1[0...i - 2]变成str2[0...j - 2], 然后将str1[i - 1]修改为str2[j - 1]
// dp[i][j] = dp[i - 1][j - 1] + 修改代价
//
//4. 当且仅当str1[i - 1] == str2[j - 1]时，将str1[0...i - 2]变成str2[0...j - 2]
// dp[i][j] = dp[i - 1][j - 1] + 0
int main_ChangeStr1ToStr2()
{
	char str1[256] = "zh";
	char str2[256] = "abdfwea";
	int insertCost = 5;
	int delCost = 3;
	int replaceCost = 2;
	int minCost = recur(str1, str2, insertCost, delCost, replaceCost, strlen(str1), strlen(str2));
	printf("%d\n", minCost);
	minCost = byStrictTable(str1, str2, insertCost, delCost, replaceCost);
	printf("%d\n", minCost);

	return 0;
}